package P1.kuaisupaixu;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @date:2022/8/17
 * @author:LdLtd
 * @name:第k个数
 */
public class QuickSort1 {
    public static void main(String [] args){
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int k=scanner.nextInt();
        int[] q=new int[n];

        for(int i=0;i< n;i++){
            q[i]=scanner.nextInt();
        }
        //返回最大的几个数
        int[] ints = new int[k];
        System.arraycopy(quick_sort(q, 0, n - 1, k),0,ints,0,k);
        System.out.println(Arrays.toString(ints));

    }
    public static int[] quick_sort(int[] q,int l,int r,int k){
        if(l==r) return q;
        int x=q[l],i=l-1,j=r+1;
        while(i<j){
            while(q[++i]>x);
            while(q[--j]<x);
            if(i<j) {
                int t=q[i];
                q[i]=q[j];
                q[j]=t;
            }


        }
        /*
        * 假设左侧元素的数目是Sl，右侧元素的数目是Sr，而且很显然，区间左侧的元素都不大于区间右侧的元素。之后根据题目中要求输入的k的大小分情况讨论：
        k<=Sl，那么整个区间里第k小的数一定在左半边，此时只需再递归处理左半边
        k>Sl，那么整个区间里第k小的数一定在右半边，此时只需要递归处理右半边，但还要再注意，在递归处理右半边的时候，不能再寻找第k小的数，而是第(k-Sl)小的数
        因此，不同于快速排序需要既递归处理左边也递归处理右边，快速选择算法不需要递归处理两边，
        * 只需要递归处理一边即可，时间复杂度就是O(N+N/2+N/4+N/8+...)，经等比数列求和，小于等于O(2N)，因此时间复杂度是O(N)*/
        int sl=j-l+1;
        if(k<=sl) return  quick_sort(q,l,j,k);
        return quick_sort(q,j+1,r,k-sl);
    }

}
